Postal services and package delivery companies typically handle as many as several million parcels each day. Automated parcel sorting and routing facilities are being used increasingly in order to improve the efficiency and accuracy with which this huge volume of parcels is handled.
In order to sort and route the parcels automatically, an image of each parcel is typically captured by a high-resolution imaging system while the parcel travels on a conveyor. An image processor must then rapidly locate and read the destination address on the parcel. This task is complicated by the fact that parcels vary greatly in size and shape, and may be placed on the conveyor for sorting in substantially any orientation. Furthermore, it frequently occurs that address blocks are located close to other text and graphic elements, as well as to tape or other shiny plastic items on the parcel, all of which add substantial “noise” to the address search. These problems are exacerbated by the fact that addresses on parcels typically contain relative few characters arranged in only a few lines, unlike text documents, which generally have redundant data. There is therefore a need for robust, high-speed methods that are capable of finding addresses in a very large, noisy image within the tight time constraints of a large-volume package sorting system.
In an article entitled, “Automatic Identification and Skew Estimation of Text Lines in Real Scene Images,” Pattern Recognition 32, pp. 791-810 (1999), which is incorporated herein by reference, Messelodi and Modena describe a method for automatically localizing text embedded in complex images. Following preprocessing, various heuristics are employed to characterize text objects which depend on the geometrical and spatial relations among more elementary components. Text line detection is accomplished by recursive nodal expansion of geometrically related components in the image to develop a tree structure.
Another approach to skew detection is disclosed by Gatos et al., in an article entitled, “Skew Detection and Text Line Position Determination in Digitized Documents,” Pattern Recognition 30, pp. 1505-1519 (1997), which is incorporated herein by reference. This approach attempts to exploit cross correlation between the pixels of vertical lines in a digitized document. A composite correlation matrix is developed for one or more vertical lines, and the skew angle of the document is evaluated from the global maximum of a projection derived from the matrix.